package leetcode_100;


/**
 *@author 周杨
 *UniquePathsII_63 动态规划走棋盘
 *describe:AC 100% 参考62题
 *2018年5月10日 下午3:46:26
 */
public class UniquePathsII_63 {
	int res=0;
	int x;
	int y;
	public static void main(String[] args) {
		UniquePathsII_63 test=new UniquePathsII_63();
		int nums[][]=new int[][] {{0,0,0},{0,1,0},{0,0,0}};
		int n[][]=new int[][] {{1,0}};
		System.out.println(test.uniquePathsWithObstacles(n));//193536720

	}
	
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		if(obstacleGrid.length==0) {//只有一行
			return 0;
		}
		if(obstacleGrid[0].length==0)
			return 0;
		int row=obstacleGrid.length;
		int col=obstacleGrid[0].length;
		int help[][]=new int[row][col];
		for(int i=0;i<row;++i) {
			if(obstacleGrid[i][0]==1) 
				break;
			else
				help[i][0]=1;
		}
		for(int i=0;i<col;++i) {
			if(obstacleGrid[0][i]==1) 
				break;
			else
				help[0][i]=1;
		}
		for(int i=1;i<row;++i)
			for(int j=1;j<col;++j) {
				if(obstacleGrid[i][j]==1) 
					help[i][j]=0;
				else
					help[i][j]=help[i-1][j]+help[i][j-1];
			}
        return help[row-1][col-1];
    }
	
	

}
